package algorithm.tree;

import java.util.Arrays;

/**
 * 哈夫曼树
 */
public class HuffmanTree {
    private int leafNum; //叶子结点个数
    private  HuffmanNode[] hnodes;//结点数组
    //构造指定权值集合的哈夫曼树
    public HuffmanTree(int[] weight) {
        int n = weight.length;
        this.leafNum = n;
        //n个叶子结点的哈夫曼树共有2n-1个结点
        this.hnodes = new HuffmanNode[2*n-1];
        for(int i=0;i<n;i++) //结点数组初始化有n叶子结点
            this.hnodes[i] = new HuffmanNode(weight[i]);
        //构造n-1个2度结点，每循环一次，构造一个2度结点
        for(int i=0;i<n-1;i++) {
            int min1,min2,x1,x2;
            min1 = min2 = Integer.MAX_VALUE;//选择最小和次最小权值，初值为最大权值
            x1 = x2 = -1;//记录两个无父母的最小权值结点下标
            for(int j=0;j<n+i;j++){
                if(hnodes[j].weight < min1 && hnodes[j].parent == -1) {
                    min2 = min1;
                    x2 = x1;
                    min1 = hnodes[j].weight;//min1记下最小权值
                    x1 = j;//x1记下次最小权值结点的下标
                }
                else if(hnodes[j].weight<min2 && hnodes[j].parent == -1) {
                    min2 = hnodes[j].weight;
                    x2 = j;//x2记下次最小权值结点的下标
                }
            }
            hnodes[x1].parent = n+i;//将找出的两棵权值最小的二叉树合并为一棵
            hnodes[x2].parent = n+i;
            this.hnodes[n+i] = new HuffmanNode();
            hnodes[n+i].weight = hnodes[x1].weight + hnodes[x2].weight;
            hnodes[n+i].left = x1;
            hnodes[n+i].right = x2;
        }
    }

    @Override
    public String toString() {
        return "HuffmanTree{" +
                "leafNum=" + leafNum +
                ", hnodes=" + Arrays.toString(hnodes) +
                '}';
    }
    //返回当前哈夫曼树的哈夫曼编码
    public String[] huffmanCode() {
        String[] code = new String[this.leafNum];
        //求n个叶子结点的哈夫曼编码
        for(int i =0;i<this.leafNum;i++){
            code[i] = "";
            int child = i;
            int parent = hnodes[child].parent;
            while (parent!=-1){ //由叶结点向上直到根结点循环
                if(hnodes[parent].left == child){
                    code[i] = "0"+code[i]; //左孩子结点编码为0
                }
                else {
                    code[i] = "1"+code[i];//右孩子编码为1
                }
                child = parent;
                parent = hnodes[child].parent;
            }
        }
        return code;
    }

    public static void main(String[] args) {
        int[] weight = {5,29,7,8,14,23,3,11};
        HuffmanTree htree = new HuffmanTree(weight);
        System.out.println("哈夫曼树的结点数组："+htree.toString());
        String[]  code = htree.huffmanCode();
        System.out.println("哈夫曼编码:");
        for (int i=0;i<code.length;i++)
            System.out.println(code[i]);
    }
}
